Part of Java Data Structures Tutorial.
[demo example][source code archive]
note: I think I may have rushed through this document, and not explain some important things thoroughly, but I do believe that if I haven't done that, then I wouldn't have finished it at all. (since I am "too" busy with my other programming right now)
I still think it's a pretty good reference, which comes with workable source to back it up... and judging from the "lack" of Binary Space Partition Tree information on the Internet, (especially relating to Java), I'd say this doc is not "that" bad.
Many approaches used in this doc, can definitely be done better, faster, and more reliably. BSPs are used in far more complex things as explained here (but they're complex, thus, not suitable for this doc ;-)
<I believe I've failed to mention the use of binary trees, where the data is not stored on the dividing nodes, but only on the leaves. This helps in high level clipping a lot, and is the technique used in Quake by id Software. After I get my C demo running (using Quake's techniques), I may write a more "professional" explanation of binary trees.>
Binary Trees are a very useful and powerful sorting and searching data structures. And since we can sort almost anything, why not sort the world?
Right now, I will stray away from Data Structures, and talk a little about Computer Graphics, and later, show how using some clever data structures, can resolve some complex computer graphics problems.
A very major problem in Computer Graphics is Hidden Surface Removal, or HSR. Think of a wire frame model...In a wire frame model, nobody can argue where's the front and where's the back... it may look many ways...
Now, think of a similar model, only with solid walls.... You automatically realize that now, the order of sides becomes important... (try imagining the "back" side of the model drawn as the front...)
No matter how you look at it, some sides cannot be seen. (some sides are behind other sides) Our mind, sorts it our for us, so that we see it "correctly."
A computer does not have a mind... It can't perceive which side is in front of which... It needs specific algorithms for everything.
There are many such HSR algorithms... One like Painter's Algorithm go trough every side, and compares it's coordinates with every other side in order to determine which one is to be draw first. All this comparing, can get quite complex and computationally expensive. Once everything is determined, you just write the farthest stuff first, and overwrite it with the closest. There also is a very popular Z-Buffering Algorithm which is a little easier to think of, but still pretty complex and can be computationally intensive. There is also Ray Tracing, which is relatively simple, but VERY computationally intensive... People have simplified it a lot by turning it into Ray Casting, the type of rendering used in Wolfestain 3D by id Software. That one, just shoots a ray (or sometimes 2 rays) across a tiled map, to determine if that tiled map has something there, if there is, it renders, it, if not, then continues with the ray... This can be very efficient, and fast, as demonstrated by Wolfenstain 3D running on my 80x286. Unfortunately, Ray Casting does not produce a "cool" looking world; most people, now a days, want to see something more than just a "blocky" world (everything in the world is made out of equal sized blocks).
To the rescue come the cool new graphics accelerators, (most of) which have Z-Buffering built in. They make the job a lot easier, and a lot faster. Eventually, when hardware becomes very advanced, nobody will even care about HSR. But at the moment, Z-Buffering hardware is only good for *a little* Z-Buffering, not a whole lot...
I mean, you would not dump dozens of thousands of polygons onto a hardware accelerator, and expect it to perform well.... you need some "higher" algorithms to remove hidden surfaces, and that's where Binary Space Partition, or BSP, comes into play.
Binary Space Partition Trees, are regular Binary Search Trees, only they sort and search space (not outer space, just virtual space). If you've read the Java Data Structures Tutorial from the beginning, you've already come across Binary Search Trees, only those were used to sort integers. The concept is almost exactly the same, only this time, instead of comparing integers, you're comparing lines or polygons. (with some *extra* partitioning. ;-)
It is important that you *understand* the structure, that way, you'll be able to use it
almost anywhere, & because I'd like to keep this explanation as simple as possible,
I'll limit the whole discussion to 2D. The same exact concepts are used in 3D, and
if you understand it in 2D, you should not have any problems with 3D (besides some weirdo
3D math of course...)
Ok, back to the ground. BSP trees are regular trees. The tree as a whole
represents all space (virtual one of course), and it's leaves (or children), represent
convex subspaces. Each node of the tree, stores information about the
"partitioning" (dividing) plane (or a line).
Now, consider a simple situation. A "viewer" is in 1 out of 2 convex rooms, in order for them to be able to draw everything correctly, they'll have to draw the other room first, then, draw the room they're in (overwriting some parts that have already been draw) (but that can be avoided with clever clipping) (or walking the BSP tree in another direction....)
So, you draw other convex space, then your own. And that's exactly what this whole BSP concept is doing. The space is sorted in a way, so that it's very easy for you to determine what is that "other" space to draw first, and what that space which should be draw last... to make everything look right.
I think I've made it look more complicated than it really is... sorry. If it helps, you can try reading the BSPFAQ available almost everywhere (and at http://www.geocities.com/SiliconValley/Way/7650 ) The BSPFAQ is not much clearer in their explanation, but at least, there, you're getting everything in proper terms... (besides, this is a Java Data Structures Tutorial, not a BSP Tree tutorial... so, lets get back to Java programming...)
(a suggestion: To understand BSP Trees, there is no better way than to practice with them, go over the source, do a simulation on paper, try different combinations... It's not easy if you don't understand it at first, but once you get the concept, it will seem crystal clear.)
The first, and most important thing we need, is a point. Everything is useless in computer graphics, if you don't have the basic building blocks. So, lets write a point class.
As you can see, this is a very basic point class, it has method to get and set the point, a copy constructor, and that's it. Very simple. Some may argue the use of set and get functions for a simple point, where these functions could be an overkill, but, this code is meant to be "optimized" by the compiler, and the "-O" option in "javac" will make all these functions inline, thus, fixing the burden associated with function calls... (hew... after looking at this source for about a minute, I've realized that I can make it better ... will go rewrite it ;-) <well... Ok, I didn't actually go and rewrite it, I've left it as it is... because I am lazy... happy?>
What we need next in our 2D bsp tree sample is a line. The line consists of 2 points, the start and end. And here's a very self explanatory line class:
This class is very self explanatory, just read the source. The only "unusual" thing in it is that "getPlane()" method, it's a method to get the "plane" of the line. Of course, there is no plane of a line... but I just named it with reference to 3D. That plane is basically the line equation, (or a vector equation?) that can be used to determine if some point is on the right or left side of the line, or better yet, in front or behind the line.
If we have a line pointing right, then the front is the "up" of the line, and the back is anything that's "down" of the line.
front
-------------->
back
And now, is the best time to present that pPlane2D class...
The plane is basically a class representing a line equation. The line equation "Ax + By = C". This class uses this equation to evaluate points in relation to that plane. There is an "eval()" function, which accepts a point, and the function returns whether the point is in front, back, or spanning of this line. There is also a similar function that accepts a line. Both of these functions use the EPSILON value to make the "plane" appear "think"... if the plane is "thin," we can get into into situations of splitting a line where it's not really needed and is not visually relevant... (what does 1/100 of a pixel do? nothing.)
The most important method in this class is the method to split the line into 2, and return the line which is in front and back of the plane. The "split()" function accepts a line as it's argument, and works by comparing the start and end of the line, in relation to the plane, (since this method should not be called if the split is not necessary, there is very minimal error checking to make sure we're splitting something that needs to be split.) It then finds the "crossing point" of the plane and the line, and sets the "front" and "back" line's coordinates, and returns and array of 2, where the first represents the "front" line and the second value in the array represents the "back" of the line.
This ability to split things, is the whole key of BSP engines, in 2D it's quite simple, in 3D, it involves a bit more math, but the idea still remains the same.
Now, since this is a Java BSP Tree Tutorial, lets write BSP classes.
First, as with a regular binary tree, we need a Node. The node should contain a partition plane, (which is pPlane2D object), and a list of lines which are spanning the plane of this node. There are many implementations of this where the lines don't necessarily span the partition plane of the node, and there are certain advantages and disadvantages to it... but this is a "simplest" tutorial, so... Anyway, where's the node class for the BSP Tree.
As you can see, it's just like a regular Binary Tree node, with 2 children, one pointing to the "front" and the other pointing to the "back" children. (for an explanation of Binary Tree Node, check out the Java Data Structures Tutorial from the start)
Now, the heart of the whole thing, the BSP Tree class!
This class heavily relies of the pQueue.java class, which I've presented in the Java Data Structures Tutorial, and will give it again in this tutorial. Now thinking about it, it would actually make more sense to use the "Vector" class provided by the JDK. The way Vector organizes it's data, would actually make it faster than Queue, (even though it "doesn't" grow dynamically, it's "arraycopy()" would be insignificant to the insertion and removal of nodes.)
Anyway, back to the subject. The 2 most important methods in this class are definitely pBuildBSPTree, which accepts Queue of lines, and pGetSortedLines, which traverses the tree, and returns a Queue of sorted lines. Now, you understand why I needed to use the Queue, or some data structure which keeps the order of things on it.
The pBuildBSPTree, recursively builds a bsp tree, given a Queue of lines. It takes 1 line of the Queue, and makes it it's "current" line, finds it's "partition plane" and sticks that partition plane into that "current" node. Then, it separates the remaining lines on the Queue, into 2 piles, with relation to the partition plane. If some line somehow ends up being on both sides, it is split. It then recursively goes through those 2 piles... and that's the whole BSP...
There are methods to "optimize" BSP Trees, and smartly choosing the partition plane (thus choosing that "line" of the Queue), can be a real significant optimization. The demo provided, just picks the first one of the Queue, but some algorithms actually go through the Queue, searching for the best one to pick... The "best" has a very loose definition, since it all depends on what you're doing exactly... usually, you'd like to have a tree with as little "depth" as possible, so, generally, you should try to avoid choosing planes that would cause lots of splits.
The other most important method is pGetSortedLines, it returns a Queue, containing all the lines, but sorted in relation to the "eye" point, and in relation to each other.
Once we have the list, we'd like to be able to draw the "farthest" lines, and then overdraw that with the "closer" lines, thus, giving us a pretty good image. This is a "derivative" of the Painter's algorithm, and it's used so much, that a lot of the people just call it "Painter's algorithm" (without even thinking that true Painter's algorithm also refers to tons of math as well... ) Because we'd like to be able to just "draw" from back to front, we "walk" the tree in a special way to generate this special sort.
Having the "eye" point, we evaluate it in relation to the partition plane of the root node, if the eye is in "front" of the partition plane, we then recursively draw the "back" child of that node, then draw the "lines" on that partition plane, and then draw the front. If however the eye is in "back" of the partition plane, we draw the "front" child of the node (recursively), then draw the lines which span that node's partition plane, and then draw the "back" child of that node. < Ouch, even I am getting confused after reading this...>
If on the other hand, we'd like to be able to draw from "front to back", (using some clever clipping technique) (with 0 overdraw), we would "walk" the tree a little differently. Having the "eye" in the "front" of the partition plane, we would first recursively draw the front, then lines spanning partition plane, and then the back... Else if eye was in "back" of the partition plane, we'd first draw the "back", then the lines spanning partition plane, and then the "front". This approach is a little bit harder to accomplish because of the complex clipping involved, but it's generally faster, because there is no overdraw, and you don't even up drawing everything, (since a lot of the things will get clipped out.)
Some notes on optimizing all this: BSP tree's can also be used to do very quick clipping, using bounding boxes; if you determine that the "front" child's bounding box is not even visible, you can avoid that "front" child altogether, (and thus avoiding tons of it's children, which you'd do recursively ...) <as far as I know, that's the technique used in Quake to speed things up.>
The 2 most important functions talked about here, are not "very friendly" to the user, so, I've created a user friendly functions, which have nothing to do with the internals of the Tree. (the user doesn't have to know about pBSPNode class to use the BSP)
Now that you know how this whole thing works, how do you use it?... good question.
I've written a couple of simple application, and 2 applets that use all this, to display a small and badly designed "world" <if it can be called that...>
Here's the general class that's using all of the above to display (anywhere), this badly designed world...
[dog.java]
This class assumes that the data has already been loaded, inserts it into the tree using the pBuildBSPTree method, and later, in a loop, gets the sorted lines, and draws them so that they appear "3D"... The class also handles user input... Requires the JDK 1.1 (because of it's JDK 1.1 event model)
Now, here's the application that loads the data, and initializes "dog" class, and makes... it's basically the "starter" class...
This class just loads the "testmap.txt" file (the map that's displayed), and creates a "dog" object to do the rest... Any applet or app can use that "dog" class, since it's quite "usable"... (I've even originally written an applet to use that as well, but realized that it's not compatible with Netscape browser, and will only with with Internet Explorer 4.
Here's an applet version of the "viewer" that uses the BSP tree... this version is NOT deprecated as of JDK 1.2, but is also not compatible with most browsers.
And who would I be if I didn't provide the compatible version... This one is VERY portable (as far as I know, it runs on anything that has Java support; tested on Internet Explorer 3 & 4, and Netscape 3 & 4.) It is however deprecated, even as of JDK 1.1... Anyway, here it is:
To make it work, just place:
<applet code="dog3dapp.class" codebase="./" width="320" height="240"></applet>into your HTML... Oh, and you can view the demo HERE! And just to be complete, here's the input file for the thing...
Oh, and I think I've forgot to include the unnecessary Queue class... here it goes, along with it's required node class...
Well... that's it folks. I'd appreciate any feedback you can give me, just e-mail me at bsptree at NO SPAM geocities dot com
© 1997-1998, Particle